#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#define INF 214748364
#define NUM_THREADS 8

int dist[1000][1000];
char v[1000];
int edges[499500][3];
int n, m;

void readMatrix() {
  int i, j;

  scanf(" %d %d", &n, &m);

  for(i=0; i<n; i++) {
    v[i] = 0;
    for(j=0; j<n; j++) {
      dist[i][j] = (i == j) ? 0 : INF;
    }
  }

  for(i=0; i<m; i++) {
    scanf(" %d %d %d", &edges[i][0], &edges[i][1], &edges[i][2]);
    edges[i][0]--; edges[i][1]--;
    v[edges[i][0]] = 1; v[edges[i][1]] = 1;
    dist[edges[i][0]][edges[i][1]] = edges[i][2];
    dist[edges[i][1]][edges[i][0]] = edges[i][2];
  }
}

void floydWarshall() {
  int i, j, k;

  for(k=0; k<n; k++) {
#pragma omp parallel for private(i,j)
    for(i=0; i<n; i++) {
      for(j=0; j<n; j++) {
        if( dist[i][j] > dist[i][k] + dist[k][j] )
          dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

int main(int argc, char *argv[]) {
  int i, j, localMax, globalMin = INF;

  if(argc == 2) {
    int num_threads = atoi(argv[1]);
    omp_set_num_threads(num_threads);
  } else {
    omp_set_num_threads(NUM_THREADS);
  }

  readMatrix();
  floydWarshall();


  for(i=0; i<n; i++) {
    localMax = 0;
    for(j=0; j<n; j++) {
      if(v[i] && v[j] && dist[i][j] > localMax)
        localMax = dist[i][j];
    }
    if (localMax < globalMin)
      globalMin = localMax;
  }

  printf("%d\n", globalMin);
  return 0;
}
